package offer.day31;

public class No52FindFirstCommonNode {
    /*
     * 面试题52：两个链表中的第一个公共节点
     * 题目：输入两个链表，找出他们的第一个公共系欸但
     * 链表节点定义：
     *  struct ListNode{
     * 		int m_nKey;
     * 		ListNode* m_pNext;
     * }
     *
     * 思路：链表1 长度为m   链表2长度为n
     * 第一种方法：蛮力法  时间复杂度O(mn)
     * 从头遍历第一个链表，和第二个链表进行对比  一样的话就是公共节点
     *
     *  第二种方法：使用辅助栈    时间复杂度O(m+n)  空间复杂度O(m+n)     空间换时间的算法
     *  对于有公共节点的单向链表来说，会成为一个Y字型的结构，从尾部进行遍历的话，
     *  直接找到第一个公共子节点就可以了，而且长度会大大缩小
     * 因为单向链表是从头进行遍历的，而从尾部进行比较会减少比较次数，这种情况很像是后进先出的情形，也就是栈的存储结构
     * 所以可以使用两个栈，对两个单向链表进行存储，然后存储后，弹出元素进行对比即可，找到最后一个相等的子节点
     *
     * 第三种方法：无辅助空间   时间复杂度O(m+n)  空间复杂度O(1)     提高了空间效率
     * 当两个链表的长度不相同时，从头节点遍历，会造成到达尾节点的时间不同，为解决这个问题，可以：
     * 1>第一次遍历两个链表得到它们的长度，算出相差多少LengthDiffer
     * 2>第二次遍历时，先将长的链表先走LengthDiffer步，然后两个链表再同步遍历，
     * 直到找到第一个相同的节点就是他们的第一个公共节点
     *
     *
     * */
    public static void main(String[] args) {
        No52FindFirstCommonNode f = new No52FindFirstCommonNode();
        ListNode one = new ListNode(1);
        ListNode two = new ListNode(2);
        ListNode three = new ListNode(3);
        ListNode four = new ListNode(4);
        ListNode five = new ListNode(5);
        ListNode six = new ListNode(6);
        ListNode seven = new ListNode(7);
        ListNode eight = new ListNode(8);
        //链表1
        one.next = three;
        three.next = five;
        five.next = six;
        //链表2
        two.next = four;
        four.next = six;
        //公共
        six.next = seven;
        seven.next = eight;
        eight.next = null;

        ListNode node1 = one;
        System.out.println("输出链表1数据：");
        for (int i = 0; i < 4; i++) {
            System.out.println(node1.val);
            node1 = node1.next;
        }
        ListNode node2 = two;
        System.out.println("输出链表2数据：");
        for (int i = 0; i < 4; i++) {
            System.out.println(node2.val);
            node2 = node2.next;
        }

        System.out.println("两个链表的第一个公共节点：");
        ListNode firstCommonNode = f.FindFirstCommonNode(one, two);

        System.out.println(firstCommonNode.val);
        System.out.println("****************************" + "两个链表的第一个公共节点" + "****************************");
    }

    private ListNode FindFirstCommonNode(ListNode head1, ListNode head2) {
        ListNode p1 = head1;
        ListNode p2 = head2;
        int size1 = 0, size2 = 0;
        while (p1 != null) {
            size1++;
            p1 = p1.next;
        }
        while (p2 != null) {
            size2++;
            p2 = p2.next;
        }
        p1=head1;
        p2=head2;
        if (size1 > size2) {
            for (int i = 0; i < size1 - size2; i++) {
                p1 = p1.next;
            }
        } else if (size1 < size2) {
            for (int i = 0; i < size2 - size1; i++) {
                p2 = p2.next;
            }
        }
        while (p1 != p2 && p1 != null && p2 != null){
            p1=p1.next;
            p2=p2.next;
        }
        return p1;
    }
}
